package leetcode.L207;


import java.util.ArrayList;
import java.util.List;

class Solution {
    List<List<Integer>> edges;
    int[] visited;
    boolean valid = true;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<List<Integer>>();
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
            //对于每个课程，初始化一个list保存边,以其为起始的边
        }
        visited = new int[numCourses];
        for (int[] info : prerequisites) {
            //保存每条以list中位置为起始点，其他点为终点的边
            edges.get(info[1]).add(info[0]);
        }
        for (int i = 0; i < numCourses && valid; i++) {
            //挨个开始遍历
            if (visited[i] == 0) {
                dfs(i);
            }
        }
        return valid;
    }

    public void dfs(int u) {
        visited[u] = 1;
        for (int v : edges.get(u)) {//从中取出以u为起点的所有边
            if (visited[v] == 0) {//若没被遍历，则遍历
                dfs(v);
                if (!valid) {//若遍历过程中发现重复，直接返回
                    return;
                }
            } else if (visited[v]==1) {
                valid = false;
                return;
            }
        }
        visited[u] = 2;//遍历了以u为起点的所有边，修改为2
    }
/*    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.canFinish(2, new int[][]{{1, 0}, {0, 1}});
    }*/

}
